#include <stdio.h>
#include <alloca.h>
#include <string.h>
#include "sort.h"
#include "heap.h"

#define swap(a, b) {\
	type_t t;\
	t = a;\
	a = b;\
	b = t;\
}

void sort_bubble(type_t arr[], int len) {
	int i,j;
	for(i = 0; i < len - 1; i ++) {
		for(j = 0; j < len - i - 1 ; j ++) {
			if(arr[j + 1] < arr[j]) {
				swap(arr[j], arr[j + 1]);
			}
		}
	}
}



int partition(type_t arr[], int left, int right) {
	type_t p = arr[right];
	int i = left - 1, j;

	for(j = left ; j < right; j ++) {
		if(arr[j] <= p) {
			i ++; // i ++ should be there
			swap(arr[i], arr[j]);
			//swap(arr[i], arr[j]); this will cause i puls 1 milti times.
		}
	}
	swap(arr[right], arr[i + 1]);
	return i + 1;
}

void _sort_quick(type_t arr[], int left, int right) {
	if(left < right) {
		int p = partition(arr, left, right);
		_sort_quick(arr, left, p - 1);
		_sort_quick(arr, p + 1, right);
	}
}

void sort_quick(type_t arr[], int len) {
	_sort_quick(arr, 0, len - 1);
}

void sort_print(type_t arr[], int len, char * tips) {
	int i;
	printf("sorted array using %s: ", tips);
	for(i = 0; i < len ; i ++ ) {
		printf("%c ", arr[i]);
	}
	printf("\n");
}



void sort_insertion(type_t arr[], int len) {
	int j, i;
	type_t key;
	for(j = 1; j < len; j ++ ) {
		key = arr[j];
		i = j - 1;
		while(i >= 0 &&  key > arr[i]) {
			arr[i + 1] = arr[i];
		}
		arr[i] = key;
	}
}


/**
 * l <= m < r
 */
void _merge(type_t arr[], int l, int m, int r) {
	int len = (r - l + 1);
	type_t * tmp = alloca(sizeof(type_t) * len);
	int i = l, j = m + 1,k = 0;
	while(i <= m && j <= r ) {
		if(arr[i] <= arr[j]) {
			tmp[k ++] = arr[i ++];
		}else{
			tmp[k ++] = arr[j ++];
		}
	}

	while(i <= m) {
		tmp[k ++] = arr[i ++];
	}

	while(j <= r) {
		tmp[k ++] = arr[j ++];
	}

	for(i = 0; i < len; i ++) {
		arr[l + i] = tmp[i];
	}
}
void _sort_merge(type_t arr[], int start, int end) {
	if(end > start) {
		int m = start + ((end - start) >> 2);
		_sort_merge(arr, start, m);
		_sort_merge(arr, m + 1, end);
		_merge(arr, start, m, end);
	}
}


void sort_merge(type_t arr[], int len) {
	_sort_merge(arr, 0, len - 1);
}


void sort_heap(type_t arr[], int len) {
	heap_t * h = heap_new(len);
	heap_appenda(h, arr, len);
	heap_build_max(h);
	while(heap_exchange(h)) {
		heapify(h, 1);
	}
	int i;
	for(i = 0; i < len; i ++) {
		arr[i] = h->data[i + 1];
	}
	heap_destroy(h);
}


void sort_selection(type_t arr[], int len) {
	int min, i, j;
	for(i = 0; i < len - 1; i ++ ) {
		min = i;
		for(j = i + 1; j < len; j ++) {
			if(arr[j] < arr[min]) {
				min = j;
			}
		}
		swap(arr[i], arr[min]);
	}
}


void sort_counting(type_t arr[], int len) {
	int * count = alloca(len * sizeof(int));
	type_t * tmp = alloca(len * sizeof(type_t));
	memcpy(tmp, arr, len * sizeof(type_t));
	memset(count, 0, len * sizeof(int));
	int i, j;
	for(i = 0; i < len - 1; i ++) {
		for(j = i + 1; j < len; j ++) {
			if(arr[i] < arr[j]) {
				count[j] ++;
			}else{
				count[i] ++;
			}
		}
	}

	for(i = 0; i < len; i ++) {
		arr[count[i]] = tmp[i];
	}
}
